import math
from collections import defaultdict
import random

class KMeans:
    def __init__(self, n_clusters=4, max_iter=100, random_state=42):
        self.n_clusters = n_clusters  # 聚类簇数
        self.max_iter = max_iter      # 最大迭代次数
        self.random_state = random_state
        self.centroids = []           # 最终聚类中心
        self.labels = []              # 每个样本的簇标签（

    def _euclidean_distance(self, x1, x2):
        return math.sqrt((x1[0] - x2[0])**2 + (x1[1] - x2[1])**2)

    def _initialize_centroids(self, X):
        random.seed(self.random_state)
        centroids = []
        sample_indices = list(range(len(X)))
        random.shuffle(sample_indices)
        for i in range(self.n_clusters):
            centroids.append(X[sample_indices[i]])
        return centroids

    def fit(self, X):
        self.centroids = self._initialize_centroids(X)

        for _ in range(self.max_iter):
            cluster_points = defaultdict(list)
            for point in X:
                distances = [self._euclidean_distance(point, cent) for cent in self.centroids]
                min_dist_idx = distances.index(min(distances))
                cluster_points[min_dist_idx].append(point)

            new_centroids = []
            for label in range(self.n_clusters):
                points_in_cluster = cluster_points.get(label, [])
                if not points_in_cluster:
                    new_centroids.append(self.centroids[label])
                    continue
                avg_x = sum(p[0] for p in points_in_cluster) / len(points_in_cluster)
                avg_y = sum(p[1] for p in points_in_cluster) / len(points_in_cluster)
                new_centroids.append([round(avg_x, 2), round(avg_y, 2)])

            if new_centroids == self.centroids:
                break
            self.centroids = new_centroids

        self.labels = []
        for point in X:
            distances = [self._euclidean_distance(point, cent) for cent in self.centroids]
            self.labels.append(distances.index(min(distances)))

        return self.labels, self.centroids

    def print_cluster_details(self, X):
        print("\n=== k-means聚类结果详情 ===")
        for cluster_label in range(self.n_clusters):
            sample_indices = [i for i, label in enumerate(self.labels) if label == cluster_label]
            sample_points = [X[i] for i in sample_indices]
            print(f"\n簇{cluster_label + 1}：")
            print(f"  聚类中心：{self.centroids[cluster_label]}")
            print(f"  包含样本索引（原数据顺序）：{sample_indices}")
            print(f"  包含样本坐标：{sample_points}")
            print(f"  簇内样本数量：{len(sample_points)}")

def load_dataset(file_path):
    X = []
    with open(file_path, 'r', encoding='utf-8') as f:
        for line_num, line in enumerate(f, 1):
            line = line.strip()
            if not line:
                continue
            try:
                x, y = map(float, line.split())
                X.append([x, y])
            except ValueError:
                print(f"警告：第{line_num}行数据格式错误（应为'数字 数字'），已跳过该行：{line}")
    return X

if __name__ == "__main__":
    dataset_path = "datasets/kmeans_data.txt"
    X = load_dataset(dataset_path)
    print(f"成功加载数据集，共{len(X)}个样本")
    print(f"数据集前5个样本：{X[:5]}")

    kmeans = KMeans(n_clusters=4, max_iter=100, random_state=42)
    labels, centroids = kmeans.fit(X)

    print("\n=== 核心聚类结果 ===")
    print(f"最终聚类中心（共{len(centroids)}个）：{centroids}")
    print(f"每个样本的簇标签（原数据顺序）：{labels}")

    kmeans.print_cluster_details(X)